The ability to detect and recognize handwritten words in handwritten documents is important for several applications. While the strategic importance of such a capability in current commercial handwriting recognition products is clear, its use in applications such as digital libraries and document management cannot be ignored. With digital libraries, for example, there is a major concern over the preservation and electronic conversion of historical paper documents. Often, these documents are handwritten and in calligraphic styles, as in a sample of a church record used in genealogy studies illustrated in FIG. 1. An important aspect of the use of electronic versions of such documents is their access based on word queries. Handwritten keyword extraction and indexing can also be a valuable capability for document management, in handling a variety of irregular paper documents such as handwritten notes, marks on engineering drawings, memos and legacy documents.
While an OCR algorithm can be used to extract text keywords for index creation of scanned printed text documents, such a process is not yet an option for handwritten documents due to a lack of robust handwriting recognition algorithms. An alternative in such situations is to avoid index creation altogether, by storing some feature-abstracted form of the bitmaps, and directly "indexing" the contents of such representations using the handwritten word query pattern. Even so, handwritten word indexing is a considerably more difficult problem than printed text indexing due to at least two reasons. First, the same query word could be written differently at different locations in a document even when the document is written by a single author. In cursive script, this often means that a word is written as a collection of word segments separated by intra-word separations that are characteristic of the author. FIGS. 2A-C illustrate this situation, where the word "database" is written by the same author differently in the various instances it occurs. Further, the different instances could exhibit different amounts of global skew, because lines of handwritten text are often not parallel as in printed text. Secondly, a detailed examination of each word location for potential matches to a query word becomes computationally expensive preventing fast retrieval of such documents.
The present method of locating handwritten words was motivated by an application that required image indexing of old calligraphic handwritten church record documents for purposes of tracing genealogy. These documents were written against a tabular background, as shown in FIG. 1. On being given a query about a person's name, the task was to locate the relevant records. While the formulation of query word patterns for these documents is an interesting problem, for the purposes of this disclosure the focus is on the problem of matching handwritten words after they have been formulated by a user--perhaps by a training process that generates such pattern queries from actual typed text queries, or perhaps such queries are derived from the handwritten document itself.
The present method of localizing handwritten word patterns in documents exploits a data structure, called the image hash table generated in a pre-processing step, to succinctly represent feature information needed to localize any word without a detailed search of the document. The use of an image hash table to localize objects draws upon ideas of geometric hashing that has been used earlier for identification of objects in pre-segmented image regions which is discussed in articles by Y. Lamdan and H. J. Wolfson entitled "Geometric hashing: A general and efficient model-based recognition scheme", in Proceeding of the International Conference on Computer Vision, pages 238-249, 1988, and "Transformation invariant indexing" in Geometric Invariants in Computer Vision, MIT Press, pages 334-352, 1992. More work has been done in extending the basic geometric hashing scheme for use with line features as described in an article by F. C. D. Tsai entitled "Geometric hashing with line features" in Pattern Recognition, Vol. 27, No. 3, pages 377-389, 1994. An extensive analysis of the geometric hashing scheme has been done in an article by W. E. L. Grimson and D. Huttenlocher entitled "On the sensitivity of geometric hashing", in Proceedings International Conference on Computer Vision, pages 334-339, 1990. Finding good geometric hash functions has also been explored in an article by G. Bebis, M. Georgiopolous and N. Lobo entitled "Learning geometric hashing functions for model-based object recognition" in Proceedings International Conference on Computer Vision, pages 543-548, 1995, and an extension of geometric hashing using the concept of rehashing the hash table has been discussed in an article by I. Rigoustos and R. Hummel "Massively parallel model matching: Geometric hashing on the connection machine" in IEEE Computer, pages 33-41, February 1992. All the prior work has used the geometric hashing technique for purposes of model indexing in object recognition where the task is to determine which of the models in a library of models is present in the indicated region in the image. The localization of handwritten words in unsegmented handwritten documents is an instance of image indexing (rather than model indexing) for which no prior work on using geometric hashing exists. The work that comes closest is the one that uses a serial search of the images for localizing handwritten words as described in an article by R. Manmatha, C. Han and E. Riseman, entitled "Word spotting: A new approach to indexing handwriting" in Proceedings IEEE Computer Vision and Pattern Recognition Conference, pages 631-637, 1996.
Disclosures of all of the references cited and/or discussed above in this Background are incorporated herein by reference for their teaching.